package cxydmmszl.chapter08.t141;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * <li style="color: red;">Prob</li>
 * 做项目的最大的收益
 * <li style="color: green;">Desc</li>
 * 给定两个整数 W 和 K，W 代表你拥有的初始资金，K 代表你最多可以做 K 个项目。
 * 再给定两个长度为 N 的正数数组 costs 和 profits，代表一共有 N 个项目，
 * costs[i] 和 profits[i] 分别表示第 i 号项目的启动资金与做完后的利润
 * (注意是利润，如果一个项目的启动资金为 10 ，利润为 4 ，代表该项目最终的收入为 14)。
 * 你不能并行只能串行地做项目，并且手里拥有的资金大于或等于某个项目的启动资金时，你才能做这个项目。
 * 该如何选择做项目，能让你最终的收益最大？返回最后能获得的最大资金。
 * <br/><br/>[要求]<br/>
 * 时间复杂度为 O(NlogN)，空间复杂度为 O(n)
 * <br/><br/>备注：<br/>
 * 1⩽K⩽N⩽10^5<br/>
 * 1⩽W, costs[i], profits[i]⩽10^9
 * <li style="color: green;">Input</li>
 * 第一行三个整数 N, W, K。表示总的项目数量，初始资金，最多可以做的项目数量；
 * 第二行有 N 个正整数，表示costs数组；
 * 第三行有 N 个正整数，表示profits数组；
 * <li style="color: green;">Output</li>
 * 输出一个整数，表示能获得的最大资金
 * <li style="color: blue;">Link</li> CD50
 *
 * @author habitplus
 * @since 2021-10-15 10:33
 */
public class Main {
    static final StreamTokenizer st =
            new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int nextInt() {
        try {
            st.nextToken();
        } catch (Exception e) {
            e.printStackTrace();
        }
        return (int) st.nval;
    }

    public static void main(String[] args) {
        int n = nextInt();
        int w = nextInt();
        int k = nextInt();
        int[][] program = new int[n][2];

        for (int i = 0; i < n; i++) program[i][0] = nextInt();
        for (int i = 0; i < n; i++) program[i][1] = nextInt();

        long ans = getMaxProfit(program, w, k);
        System.out.println(ans);
    }

    private static long getMaxProfit(int[][] program, int w, int k) {
        if (program == null || program.length == 0
                || program[0].length == 0 || k < 1 || w < 1)
            return 0;

        // 小顶堆，每个项目按启动资金入堆，则堆顶一定是当前所有项目中启动资金最小的项目
        PriorityQueue<int[]> minCostHeap = new PriorityQueue<>((o1, o2) -> o1[0] - o2[0]);
        // 大顶堆，项目按利润入堆，则堆顶一定是当前所有能启动的项目中获得利润最大的项目
        PriorityQueue<int[]> maxProfitHeap = new PriorityQueue<>((o1, o2) -> o2[1] - o1[1]);

        // 开始前全部项目加入小顶堆
        for (int[] pro : program) minCostHeap.add(pro);

        long res = w;
        for (int i = 0; i < k; i++) {
            // 将当前初始资金下，所能完成的项目全部加入大顶堆
            while (!minCostHeap.isEmpty() && minCostHeap.peek()[0] < res) {
                maxProfitHeap.add(minCostHeap.poll());
            }

            // 当前初始资金下没有能完成的项目
            if (maxProfitHeap.isEmpty()) {
                break;
            }

            int[] p = maxProfitHeap.poll();
            res += p[1];
        }

        return res;
    }
}
